package com.cb2.algorithm.leetcode;

/**
 * <a href='https://leetcode.cn/problems/design-front-middle-back-queue'>找出临界点之间的最小和最大距离(Find the Minimum and Maximum Number of Nodes Between Critical Points)</a>
 * <p>链表中的 临界点 定义为一个 局部极大值点 或 局部极小值点 。</p>
 * <p>如果当前节点的值 严格大于 前一个节点和后一个节点，那么这个节点就是一个  局部极大值点 。</p>
 * <p>如果当前节点的值 严格小于 前一个节点和后一个节点，那么这个节点就是一个  局部极小值点 。</p>
 * <p>注意：节点只有在同时存在前一个节点和后一个节点的情况下，才能成为一个 局部极大值点 / 极小值点 。</p>
 * <p>给你一个链表 head ，返回一个长度为 2 的数组 [minDistance, maxDistance] ，其中 minDistance 是任意两个不同临界点之间的最小距离，maxDistance 是任意两个不同临界点之间的最大距离。如果临界点少于两个，则返回 [-1，-1] 。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：head = [3,1]
 *      输出：[-1,-1]
 *      解释：链表 [3,1] 中不存在临界点。
 *
 * 示例 2：
 *      输入：head = [5,3,1,2,5,1,2]
 *      输出：[1,3]
 *      解释：存在三个临界点：
 *          - [5,3,1,2,5,1,2]：第三个节点是一个局部极小值点，因为 1 比 3 和 2 小。
 *          - [5,3,1,2,5,1,2]：第五个节点是一个局部极大值点，因为 5 比 2 和 1 大。
 *          - [5,3,1,2,5,1,2]：第六个节点是一个局部极小值点，因为 1 比 5 和 2 小。
 *          第五个节点和第六个节点之间距离最小。minDistance = 6 - 5 = 1 。
 *          第三个节点和第六个节点之间距离最大。maxDistance = 6 - 3 = 3 。
 *
 * 示例 3：
 *      输入：head = [1,3,2,2,3,2,2,2,7]
 *      输出：[3,3]
 *      解释：存在两个临界点：
 *          - [1,3,2,2,3,2,2,2,7]：第二个节点是一个局部极大值点，因为 3 比 1 和 2 大。
 *          - [1,3,2,2,3,2,2,2,7]：第五个节点是一个局部极大值点，因为 3 比 2 和 2 大。
 *          最小和最大距离都存在于第二个节点和第五个节点之间。
 *          因此，minDistance 和 maxDistance 是 5 - 2 = 3 。
 *          注意，最后一个节点不算一个局部极大值点，因为它之后就没有节点了。
 *
 * 示例 4：
 *      输入：head = [2,3,3,2]
 *      输出：[-1,-1]
 *      解释：链表 [2,3,3,2] 中不存在临界点。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>链表中节点的数量在范围 [2, 10^5] 内</li>
 *      <li>1 <= Node.val <= 10^5</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/12/11 13:54
 */
public class LC2058FindMinimumAndMaximumNumberOfNodesBetweenCriticalPoints_M {
    static class Solution {
        public int[] nodesBetweenCriticalPoints(ListNode head) {
            int minDistance = Integer.MAX_VALUE;
            int firstPointIndex = -1;   // 第一个临界值的位置
            int prevPointIndex = -1;    // 上一个临界值的位置
            int idx = 1;
            int prevNodeVal = head.val;
            ListNode currNode = head.next;
            while (currNode.next != null) {
                int nextNodeVal = currNode.next.val;
                // 找到一个临界点
                if ((currNode.val < prevNodeVal && currNode.val < nextNodeVal) || (currNode.val > prevNodeVal && currNode.val > nextNodeVal)) {
                    // 第一次找到临界点
                    if (firstPointIndex == -1) {
                        firstPointIndex = idx;
                    }
                    // 多次找到临界点
                    else {
                        minDistance = Math.min(minDistance, idx - prevPointIndex);
                    }
                    prevPointIndex = idx;
                }
                ++idx;
                prevNodeVal = currNode.val;
                currNode = currNode.next;
            }
            if (firstPointIndex == prevPointIndex) {
                return new int[]{-1, -1};
            }
            return new int[]{minDistance, prevPointIndex - firstPointIndex};
        }
    }

    public static void main(String[] args) {
        ListNode head1 = new ListNode(3);
        head1.next = new ListNode(1);

        ListNode head2 = new ListNode(5);
        head2.next = new ListNode(3);
        head2.next.next = new ListNode(1);
        head2.next.next.next = new ListNode(2);
        head2.next.next.next.next = new ListNode(5);
        head2.next.next.next.next.next = new ListNode(1);
        head2.next.next.next.next.next.next = new ListNode(2);

        ListNode head3 = new ListNode(1);
        head3.next = new ListNode(3);
        head3.next.next = new ListNode(2);
        head3.next.next.next = new ListNode(2);
        head3.next.next.next.next = new ListNode(3);
        head3.next.next.next.next.next = new ListNode(2);
        head3.next.next.next.next.next.next = new ListNode(2);
        head3.next.next.next.next.next.next.next = new ListNode(2);
        head3.next.next.next.next.next.next.next.next = new ListNode(7);

        ListNode head4 = new ListNode(2);
        head4.next = new ListNode(3);
        head4.next.next = new ListNode(3);
        head4.next.next.next = new ListNode(2);

        Solution solution = new Solution();
        Printer.printArrayInt(solution.nodesBetweenCriticalPoints(head1));
        Printer.printArrayInt(solution.nodesBetweenCriticalPoints(head2));
        Printer.printArrayInt(solution.nodesBetweenCriticalPoints(head3));
        Printer.printArrayInt(solution.nodesBetweenCriticalPoints(head4));
    }
}
